package org.example.ch04;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/combinations/
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 你可以按 任何顺序 返回答案
 * 输入：n = 4, k = 2
 * 输出：
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 */
public class Combine {


    public static void main(String[] args) {

        Combine com = new Combine();
       List<List<Integer>> list =  com.combine(4,2);
        for (int i = 0; i < list.size(); i++) {
            for (Integer num:list.get(i)){
                System.out.print(num+" ");
            }
            System.out.println();
        }
    }

    public List<List<Integer>> combine(int n,int k){
      Deque<Integer> queue = new ArrayDeque<Integer>();

      List<List<Integer>> res = new ArrayList<>();
      int begin=1;
      dfs(n,k,begin,queue,res);

      return res;
    }

    /**
     * [1,2,3,4]
     * 深度优先遍历
     * @param n
     * @param k
     * @param begin
     * @param path
     * @param res
     */
    public void  dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        //递归的终止条件
        if(path.size()==k){
            res.add(new ArrayList<>(path));
            return;
        }
        //执行本层逻辑
        for (int i = begin; i <= n; i++) {
            path.addLast(i);
            //下探到下一层递归，传入主角
            begin=begin+1;
            dfs(n,k,begin,path,res);
            //清理本层
            path.removeLast();
        }


    }
}
